package com.ha7419x;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int arr[]={4,7,6,5,3,2,8,1};
        quickSort(arr,0,7);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int arr[],int startIndex,int endIndex){
        //递归结束条件为startIndex大于或等于endIndex
        if(startIndex>=endIndex){
            return;
        }

        //得到基准元素位置
        int pIndex=partition(arr,startIndex,endIndex);

        //根据基准元素分两部分进行递归排序
        quickSort(arr,startIndex,pIndex-1);
        quickSort(arr,pIndex+1,endIndex);
    }
    /*
     * 分治法（双边循环法）
     * arr  待排序数组
     * startIndex  起始下标
     * endIndex  结束下标
     * */
    public static int partition(int arr[],int startIndex,int endIndex)
    {
        int p=arr[startIndex];//基准元素(可取随机位置)
        int l=startIndex;//左指针
        int r=endIndex;//右指针

        while(l!=r){
            //控制右指针向左移动，找到小于基准元素的那个数
            while((l<r)&&(arr[r]>p)){
                r--;
            }
            //控制左指针向右移动，找到大于基准元素的那个数
            while((l<r)&&(arr[l]<=p)){
                l++;
            }
            //交换l指针和r指针所指的元素
            if(l<r){
                int tmp=arr[l];
                arr[l]=arr[r];
                arr[r]=tmp;
            }
        }

        //交换基准元素和重合点的元素
        arr[startIndex]=arr[l];
        arr[l]=p;
        return l;
    }

}
